// the result is basically same as kmeans, but the running time is very long
// need some improvement to speed up
package roman.algorithm;

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Scanner;

public class LocalSearch {
	Random rd = new Random(System.currentTimeMillis());
	int dataLength = 10000;
	double[] x;
	double[] y;
	int k = 4;
	// in this case the center only stores the index
	int[] center = new int[k];
	int[] belongTo;
	
	public void search(){
		double objectValue = 0;
		double tmpObjective=0;
		int tmpU = -1;	// the point in the set
		int tmpV = -1;	// the point out of the set
		int tmp;
		double prevObjectValue = findObjectiveValue();
		while(true){
			objectValue = findObjectiveValue();
			for(int i =0; i<k; i++){
				for(int j=0; j<dataLength; j++){
					tmp = center[i];
					if(j!=center[i]){
						center[i]=j;
						tmpObjective = findObjectiveValue();
						if(tmpObjective < objectValue){
							objectValue = tmpObjective;
							tmpU = i;
							tmpV = j;
						}
					}
					center[i]=tmp;
				}
			}
			center[tmpU]=tmpV;
			System.out.println(objectValue);
			if(Math.abs(prevObjectValue-objectValue)<5){
				break;
			}
			prevObjectValue = objectValue;
		}
	}
	public double findObjectiveValue(){
		double objectiveValue = 0;
		double[] dist = new double[k];
		for(int i =0; i<dataLength; i++){
			for(int j = 0; j<k;j++){
				dist[j] = Math.sqrt((x[i]-x[center[j]])*(x[i]-x[center[j]])+(y[i]-y[center[j]])*(y[i]-y[center[j]]));
			}
			int index = 0;
			for(int j = 0; j<k; j++){
				if(dist[index]>dist[j]){
					index = j;
				}
			}
			objectiveValue += dist[index];
			belongTo[i]=index;
		}
		return objectiveValue;
	}
	public void output() throws IOException{
		findObjectiveValue();
		PrintWriter pw1 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_1")));
		PrintWriter pw2 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_2")));
		PrintWriter pw3 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_3")));
		PrintWriter pw4 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_4")));
		for(int i=0; i<dataLength; i++){
			if(belongTo[i]==0){
				pw1.println("1"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==1){
				pw2.println("2"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==2){
				pw3.println("3"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==3){
				pw4.println("4"+" "+x[i]+" "+y[i]);
				continue;
			}
		}
		pw1.flush();
		pw1.close();
		pw2.flush();
		pw2.close();
		pw3.flush();
		pw3.close();
		pw4.flush();
		pw4.close();
	}
	public void process() throws IOException{
		Scanner sc = new Scanner(new FileInputStream("testdata\\data0"));
		x = new double[dataLength];
		y = new double[dataLength];
		belongTo = new int[dataLength];
		int counter = 0;
		int tmp;

		while(sc.hasNext()){
			x[counter] = sc.nextDouble();
			y[counter] = sc.nextDouble();
			counter++;
		}
		for(int i=0; i<dataLength;i++){
			belongTo[i]=k+1;
		}
		for(int i =0; i<k; i++){
			tmp = rd.nextInt(dataLength);
			center[i]=tmp;
		}
		search();
		output();
	}
	public static void main(String[] argv) throws IOException{
		LocalSearch o = new LocalSearch();
		o.process();
	}
}
